/* Module implements a 3 dimensional searching algorithmn
   Created 25.01.2003 T. Milius
   Changed 11.09.2004 T. Milius */
/* (c) Copyright 2003-2004 by Thomas Milius Stade, Germany
   Source must not be altered without agreement of the owner.
   The owner of the source is allowed to use this code inside programs without
   publishing the code of this programs. These programs may be commercial.
   Other developers can use this source freely inside own software if the source
   code of this programs is made public to same conditions like valid to this code
   and no commercial profit is taken from the programs based on this code

   Code or parts of it are not allowed to be used within GPL code or
   similar licenses which are "infecting" other code and trying to "supersede"
   other licenses. */
/* ANSI-C */

#ifndef rngsearch_h
#define rngsearch_h

/* !!!!!!!!!! libraries !!!!!!!!!! */
/* ---------- own ---------- */
#include "mem_manag.h"
#include "colour_groups.h"

/* !!!!!!!!!! definitions !!!!!!!!!! */
/* to clarify reading */
#ifndef FALSE
#define FALSE 0
#endif

#ifndef TRUE
#define TRUE 1
#endif

#define MAX_COLOUR_LIST_ELEMENTS 4000
#define MAX_COLOUR_SEARCH_ELEMENTS 4000

#define NUMBER_OF_DITHER_LINE_OFFSETS 256
#define NUMBER_OF_OCCURANCES 256

//#define RNGS_TRACE_MODE

/* !!!!!!!!!! data structures !!!!!!!!!! */
struct colour_combination_struct {
struct colour_combination_struct *next_list_element;
unsigned long group_mask;
unsigned long colour_mapping;
unsigned long paper_colour_fraction;
long colour[3];
/* 3 Dimensions will lead to an unaceptable number of elements */
long span[1][2];
};

struct colour_list_storage_struct {
struct colour_list_storage_struct *next_list_element_storage;
int no_of_used_elements;
struct colour_combination_struct list_element[MAX_COLOUR_LIST_ELEMENTS];
};

struct colour_search_element_struct {
struct colour_combination_struct *colour_list;
long level;
/* 3 Dimensions will lead to an unaceptable number of elements */
long mid_of_span[2];
struct colour_search_element_struct *sub_element[2][2];
};

struct colour_search_storage_struct {
struct colour_search_storage_struct *next_search_element_storage;
int no_of_used_elements;
struct colour_search_element_struct search_element[MAX_COLOUR_SEARCH_ELEMENTS];
};

struct dither_calculation {
struct colour_combination_struct *original_colour;
long total_usage_percentage;
long occurrance;
long relation_factor;
long position;
long integer_factor;
};

struct colour_search_struct {
struct colour_list_storage_struct *first_list_element_storage;
struct colour_search_storage_struct *first_search_element_storage;
struct colour_search_element_struct *top_search_element;
int dynamic_area;
/* Array of integer is job independent and stored elsewhere */
int *line_offset;
int actual_line;
/* internal states used by find_best_colour in a static
   way between procedure calls */
long last_colour_component[3];
long base_factor;
/* 8 for one element of each cube and 1 for possible paper colour */
struct dither_calculation dither_list[9];
struct colour_combination_struct *paper_colour;
int dither_list_pos;
long approximation_remain;
int approximation_valid;
/* Debugging purposes */
int trace_file;
};

struct searchable_range {
long span[3][2];
unsigned long group_mask;
unsigned long colour_mapping;
long colour[3];
unsigned long paper_colour_fraction;
};

struct best_value_around {
long best_colour_distance;
struct colour_combination_struct *best_colour;
};

struct occurance_calculation {
struct colour_combination_struct *original_colour;
long colour[3];
long local_usage_percentage;
};

/* !!!!!!!!!! support functions !!!!!!!!!! */
/* The dither information is dumper specific not job specific.
   The data is allocated inside the dumper which also manages
   the relase of the structure.
   However the data is used only inside this searching. Therefore
   the procedure to fill the data has been located here. */
int load_dither_information(char *dither_info_file_name,
                            int dynamic_area,
                            int **line_offset)
{
int i, j;
int value;
char value_type[10];
FILE *dither_info_file;

if ((*line_offset=dumper_malloc(dynamic_area,
                                NUMBER_OF_DITHER_LINE_OFFSETS*NUMBER_OF_OCCURANCES*sizeof(int))) == NULL) {
  return FALSE;
  }
/* Prepare Arrays */
for (i=0; i < NUMBER_OF_DITHER_LINE_OFFSETS; i++) {
  for (j=0; j < NUMBER_OF_OCCURANCES; j++) {
    (*line_offset)[(i*NUMBER_OF_OCCURANCES) + j]=0;
    }
  }
if ((dither_info_file=fopen(dither_info_file_name, "r")) == NULL) {
  return FALSE;
  }
while(!feof(dither_info_file)) {
  if (fscanf(dither_info_file,
             "%[^,],%d,%d,%d\n",
             value_type,
             &i,
             &j,
             &value) == 4) {
    if (strcmp(value_type, "ho") == 0) {
      if ((i >= 0) &&
          (i < NUMBER_OF_DITHER_LINE_OFFSETS) &&
          (j >= 0) &&
          (j < NUMBER_OF_OCCURANCES)) {
        (*line_offset)[(i*NUMBER_OF_OCCURANCES) + j]=value;
        }
      }
    }
  }
fclose(dither_info_file);
return TRUE;
}

struct colour_combination_struct *get_free_list_element(struct colour_search_struct *search)
{
struct colour_combination_struct *new_list_element;
struct colour_list_storage_struct *new_block;

if ((search->first_list_element_storage == NULL) ||
    (search->first_list_element_storage->no_of_used_elements >= MAX_COLOUR_LIST_ELEMENTS)) {
  if ((new_block=dumper_malloc(search->dynamic_area,
                               sizeof(struct colour_list_storage_struct))) == NULL) {
    return NULL;
    }
  new_block->next_list_element_storage=search->first_list_element_storage;
  search->first_list_element_storage=new_block;
  new_block->no_of_used_elements=0;
  }
new_list_element=&search->first_list_element_storage->list_element[search->first_list_element_storage->no_of_used_elements];
search->first_list_element_storage->no_of_used_elements++;
new_list_element->next_list_element=NULL;
return new_list_element;
}

struct colour_search_element_struct *get_free_search_element(struct colour_search_struct *search)
{
struct colour_search_element_struct *new_search_element;
struct colour_search_storage_struct *new_block;

if ((search->first_search_element_storage == NULL) ||
    (search->first_search_element_storage->no_of_used_elements >= MAX_COLOUR_SEARCH_ELEMENTS)) {
  if ((new_block=dumper_malloc(search->dynamic_area,
                               sizeof(struct colour_search_storage_struct))) == NULL) {
    return NULL;
    }
  new_block->next_search_element_storage=search->first_search_element_storage;
  search->first_search_element_storage=new_block;
  new_block->no_of_used_elements=0;
  }
new_search_element=&search->first_search_element_storage->search_element[search->first_search_element_storage->no_of_used_elements];
search->first_search_element_storage->no_of_used_elements++;
new_search_element->sub_element[0][0]=NULL;
new_search_element->sub_element[0][1]=NULL;
new_search_element->sub_element[1][0]=NULL;
new_search_element->sub_element[1][1]=NULL;
new_search_element->colour_list=NULL;
return new_search_element;
}

int insert_search_range_i(struct colour_search_element_struct *act_search_element,
                          struct searchable_range *new_range,
                          struct colour_search_struct *search)
{
int x_i, y_i;
long x_start, x_end, y_start, y_end;
int result;
long level;
struct colour_search_element_struct *new_search_element;
struct colour_combination_struct *new_list_element;

/* Check, whether new range covers the element entirely */
result=TRUE;
level=act_search_element->level;
if ((new_range->span[0][0] <= (act_search_element->mid_of_span[0] - level)) &&
    ((act_search_element->mid_of_span[0] + level - 1) <= new_range->span[0][1]) &&
    (new_range->span[1][0] <= (act_search_element->mid_of_span[1] - level)) &&
    ((act_search_element->mid_of_span[1] + level - 1) <= new_range->span[1][1])) {
  /* Insert range into list of this search element */
  if ((new_list_element=get_free_list_element(search)) != NULL) {
    /* add to search element list */
    new_list_element->next_list_element=act_search_element->colour_list;
    act_search_element->colour_list=new_list_element;
    /* store colour information */
    new_list_element->group_mask=new_range->group_mask;
    new_list_element->colour_mapping=new_range->colour_mapping;
    /* Must be converted to 12 Bit multipier */
    new_list_element->paper_colour_fraction=(new_range->paper_colour_fraction<<12)/100;
    new_list_element->colour[0]=new_range->colour[0];
    new_list_element->colour[1]=new_range->colour[1];
    new_list_element->colour[2]=new_range->colour[2];
    new_list_element->span[0][0]=new_range->span[2][0];
    new_list_element->span[0][1]=new_range->span[2][1];
    /* Note one entry of paper colour */
    if ((!search->paper_colour) &&
        ((new_list_element->group_mask & COLOUR_GROUP_PAPER_COLOUR) != 0)) {
      search->paper_colour=new_list_element;
      }
    }
  else {
    /* No free list element */
    result=FALSE;
    }
  }
else {
  /* Note: logically you can't cover a span of level 0
     and then did not claim it. So there is not need
     to check for level 0 at here */
  /* Check which sub search elements are touched by the range

     nr_s <= ss_s & ss_s <= nr_e -> covered
     nr_s <= ss_e & ss_e <= nr_e -> covered
     ss_s <  nr_s & nr_e <= ss_e -> covered

     This is valid for all dimensions */
  for (x_i=0; x_i < 2; x_i++) {
    if (x_i == 0) {
      x_start=act_search_element->mid_of_span[0] - level;
      x_end=act_search_element->mid_of_span[0] - 1;
      }
    else {
      x_start=act_search_element->mid_of_span[0];
      x_end=act_search_element->mid_of_span[0] + level - 1;
      }
    if (((new_range->span[0][0] <= x_start) &&
         (x_start <= new_range->span[0][1])) ||
        ((new_range->span[0][0] <= x_end) &&
         (x_end <= new_range->span[0][1])) ||
        ((x_start <= new_range->span[0][0]) &&
         (new_range->span[0][1] <= x_end))) {
      for (y_i=0; y_i < 2; y_i++) {
        if (y_i == 0) {
          y_start=act_search_element->mid_of_span[1] - level;
          y_end=act_search_element->mid_of_span[1] - 1;
          }
        else {
          y_start=act_search_element->mid_of_span[1];
          y_end=act_search_element->mid_of_span[1] + level - 1;
          }
        if (((new_range->span[1][0] <= y_start) &&
             (y_start <= new_range->span[1][1])) ||
            ((new_range->span[1][0] <= y_end) &&
             (y_end <= new_range->span[1][1])) ||
            ((y_start <= new_range->span[1][0]) &&
             (new_range->span[1][1] <= y_end))) {
          /* Check whether Search element exists */
          if (!act_search_element->sub_element[x_i][y_i]) {
            if ((new_search_element=get_free_search_element(search)) != NULL) {
              act_search_element->sub_element[x_i][y_i]=new_search_element;
              new_search_element->level=level/2;
              new_search_element->mid_of_span[0]=x_start + new_search_element->level;
              new_search_element->mid_of_span[1]=y_start + new_search_element->level;
              }
            }
          if (act_search_element->sub_element[x_i][y_i]) {
            if (!insert_search_range_i(act_search_element->sub_element[x_i][y_i],
                                       new_range,
                                       search)) {
              result=FALSE;
              }
            }
          else {
            result=FALSE;
            }
          }
        }
      }
    }
  }
return result;
}

/* !!!!!!!!!! functions !!!!!!!!!! */
int initialize_search_range(struct colour_search_struct *search,
                            int dynamic_area,
                            int *line_offset,
                            int trace_file)
{

search->first_list_element_storage=NULL;
search->first_search_element_storage=NULL;
search->top_search_element=NULL;
search->dynamic_area=dynamic_area;
search->actual_line=0;
search->line_offset=line_offset;
search->paper_colour=NULL;
#ifdef RNGS_TRACE_MODE
search->trace_file=trace_file;
#endif
return TRUE;
}

int drop_search_range(struct colour_search_struct *search)
{
struct colour_list_storage_struct *actual_list_element_storage, *next_list_element_storage;
struct colour_search_storage_struct *actual_search_element_storage, *next_search_element_storage;

if (!search) return FALSE;
actual_list_element_storage=search->first_list_element_storage;
while(actual_list_element_storage) {
  /* needed because actual_list_element_storage is freed */
  next_list_element_storage=actual_list_element_storage->next_list_element_storage;
  dumper_free(search->dynamic_area,
              actual_list_element_storage);
  actual_list_element_storage=next_list_element_storage;
  }
actual_search_element_storage=search->first_search_element_storage;
while(actual_search_element_storage) {
  /* needed because actual_list_element_storage is freed */
  next_search_element_storage=actual_search_element_storage->next_search_element_storage;
  dumper_free(search->dynamic_area,
              actual_search_element_storage);
  actual_search_element_storage=next_search_element_storage;
  }
initialize_search_range(search,
                        search->dynamic_area,
                        search->line_offset,
                        search->trace_file);
return TRUE;
}

int insert_search_range(struct searchable_range *new_range,
                        struct colour_search_struct *search)
{
struct colour_search_element_struct *new_search_element;

if (!search->top_search_element) {
  if ((new_search_element=get_free_search_element(search)) != NULL) {
    search->top_search_element=new_search_element;
    new_search_element->level=128;
    new_search_element->mid_of_span[0]=new_search_element->level;
    new_search_element->mid_of_span[1]=new_search_element->level;
    }
  }
if (search->top_search_element) {
  return insert_search_range_i(search->top_search_element,
                               new_range,
                               search);
  }
else {
  return FALSE;
  }
}

int start_dithering(struct colour_search_struct *search)
{

search->approximation_valid=FALSE;
return TRUE;
}

/* The search tree is scanned:
   Go down straight forward through the tree. At every
   node the according list must be evalutated for results.

   The eight nearest colours are stored, one for each edge
   of the cube around the wanted colour. Afterwards percentages
   of occurance depending on the distances of the found colours
   from the required colour are calculated.

   At the end one of the stored colours is choosen depending
   on its percentage of occurance and the column pixel position
   in the line. */
unsigned long find_best_colour(struct colour_search_struct *search,
                               long x_value,
                               long y_value,
                               long z_value,
                               unsigned long pixel_position,
                               unsigned long default_mapping,
                               long mode,
                               int black_mode_flag)
{
int colour_found_flag;
int i, x_i, y_i;
long diff, diff_x, diff_y, diff_z;
long act_distance, old_ref_distance;
unsigned long group_selection_mask;
struct colour_combination_struct *best_colour[8];
int number_of_best_colours;
struct best_value_around best_quarder_colour[8];
struct occurance_calculation occurance_list[8];
int occurance_list_pos;
struct colour_search_element_struct *act_search_element;
struct colour_combination_struct *act_list_element;
int distance_sort[9];
int distance_sort_elements;
long main_factor;
long max_percentage;
long min_position, max_position;
long line_position_offset;
long actual_sum;
struct dither_calculation *dither_paper_colour;
struct dither_calculation *actual_dither_list_element;
long dither_paper_colour_fraction;
long actual_dither_paper_colour_fraction;
#ifdef RNGS_TRACE_MODE
char trace_string[500];
_kernel_swi_regs regs;
#endif

if (mode == 2) {
  return x_value | (y_value<<8) | (z_value<<16);
  }
/* Must be in range between 1-256. */
pixel_position=(pixel_position & 0x000000FF);
pixel_position++;
if (search->approximation_valid) {
  /* Always use old approximation if colours are identical.
     Also use approximation if colours are nearly the same
     and an approximation cycle is still pending. */
  /* Calculate colour difference */
  if (search->last_colour_component[0] >= x_value) {
    actual_sum=search->last_colour_component[0] - x_value;
    }
  else {
    actual_sum=x_value - search->last_colour_component[0];
    }
  if (search->last_colour_component[1] >= y_value) {
    actual_sum+=search->last_colour_component[1] - y_value;
    }
  else {
    actual_sum+=y_value - search->last_colour_component[1];
    }
  if (search->last_colour_component[2] >= z_value) {
    actual_sum+=search->last_colour_component[2] - z_value;
    }
  else {
    actual_sum+=z_value - search->last_colour_component[2];
    }
  if ((actual_sum != 0) &&
      ((search->approximation_remain < 1) ||
       (actual_sum > 6))) {
    search->approximation_valid=FALSE;
    }
  if (search->approximation_remain > 0) {
    search->approximation_remain--;
    }
  }
if (!search->approximation_valid) {
  /* Initialize best colour selection */
  for (i=0; i < 8; i++) {
    best_quarder_colour[i].best_colour_distance=0x07FFFFFF;
    best_quarder_colour[i].best_colour=NULL;
    }
  /* Black group only filter */
  if (black_mode_flag &&
      (x_value == y_value) &&
      (y_value == z_value)) {
    group_selection_mask=COLOUR_GROUP_BLACK_MODE;
    }
  else {
    group_selection_mask=COLOUR_GROUP_ALL_COLOURS;
    }
  colour_found_flag=FALSE;
  /* Go down through range search structure to the required
     colour */
#ifdef RNGS_TRACE_MODE
  sprintf(trace_string,
          "Required colour RGB: %ld %ld %ld Selectionmask: %lx\n",
          x_value,
          y_value,
          z_value,
          group_selection_mask);
  regs.r[0]=2;
  regs.r[1]=search->trace_file;
  regs.r[2]=(int) trace_string;
  regs.r[3]=strlen(trace_string);
  _kernel_swi(OS_GBPB, &regs, &regs);
#endif
  act_search_element=search->top_search_element;
  while (act_search_element) {
#ifdef RNGS_TRACE_MODE
    sprintf(trace_string,
            "lev: %ld x: %ld %ld y: %ld %ld\n",
            act_search_element->level,
            act_search_element->mid_of_span[0] - act_search_element->level,
            act_search_element->mid_of_span[0] + act_search_element->level - 1,
            act_search_element->mid_of_span[1] - act_search_element->level,
            act_search_element->mid_of_span[1] + act_search_element->level - 1);
    regs.r[0]=2;
    regs.r[1]=search->trace_file;
    regs.r[2]=(int) trace_string;
    regs.r[3]=strlen(trace_string);
    _kernel_swi(OS_GBPB, &regs, &regs);
#endif
    /* Check the points inside the colour list attached to this
       point */
    act_list_element=act_search_element->colour_list;
    while(act_list_element) {
      /* Filter 3. Dimension and
         group mask */
      if ((act_list_element->span[0][0] <= z_value) &&
          (z_value <= act_list_element->span[0][1]) &&
          ((act_list_element->group_mask & group_selection_mask) != 0)) {
        /* Calculate distance from target point to point inside
           the list */
        diff=act_list_element->colour[0] - x_value;
        act_distance=diff*diff;
        diff=act_list_element->colour[1] - y_value;
        act_distance+=diff*diff;
        diff=act_list_element->colour[2] - z_value;
        act_distance+=diff*diff;
        /* Look if actual colour is the nearest one until now
           inside a certain part of the cube around
           the search colour. */
        /* Check for exact matching */
        if ((act_distance == 0) &&
            (act_list_element->paper_colour_fraction == 0)) {
#ifdef RNGS_TRACE_MODE
          sprintf(trace_string,
                  "match: s: %ld %ld RGB: %ld %ld %ld gm: %lx %lx\n",
                  act_list_element->span[0][0],
                  act_list_element->span[0][1],
                  act_list_element->colour[0],
                  act_list_element->colour[1],
                  act_list_element->colour[2],
                  act_list_element->group_mask,
                  act_list_element->colour_mapping);
          regs.r[0]=2;
          regs.r[1]=search->trace_file;
          regs.r[2]=(int) trace_string;
          regs.r[3]=strlen(trace_string);
          _kernel_swi(OS_GBPB, &regs, &regs);
#endif
          search->approximation_valid=FALSE;
          if (mode == 3) {
            return act_list_element->colour[0] | (act_list_element->colour[1]<<8) | (act_list_element->colour[2]<<16);
            }
          else {
            return act_list_element->colour_mapping;
            }
          }
        /* Determine part of cube */
        if (act_list_element->colour[0] < x_value) {
          i=0;
          }
        else {
          i=4;
          }
        if (act_list_element->colour[1] >= y_value) {
          i+=2;
          }
        if (act_list_element->colour[2] >= z_value) {
          i+=1;
          }
        /* Check for nearest distance */
        if (best_quarder_colour[i].best_colour_distance > act_distance) {
          colour_found_flag=TRUE;
          best_quarder_colour[i].best_colour_distance=act_distance;
          best_quarder_colour[i].best_colour=act_list_element;
#ifdef RNGS_TRACE_MODE
          sprintf(trace_string,
                  "note: %d s: %ld %ld RGB: %ld %ld %ld gm: %lx %lx\n",
                  i,
                  act_list_element->span[0][0],
                  act_list_element->span[0][1],
                  act_list_element->colour[0],
                  act_list_element->colour[1],
                  act_list_element->colour[2],
                  act_list_element->group_mask,
                  act_list_element->colour_mapping);
          regs.r[0]=2;
          regs.r[1]=search->trace_file;
          regs.r[2]=(int) trace_string;
          regs.r[3]=strlen(trace_string);
          _kernel_swi(OS_GBPB, &regs, &regs);
#endif
          }
        }
      /* Next colour */
      act_list_element=act_list_element->next_list_element;
      }
    /* Choose the next sub search element */
    if (x_value < act_search_element->mid_of_span[0]) {
      x_i=0;
      }
    else {
      x_i=1;
      }
    if (y_value < act_search_element->mid_of_span[1]) {
      y_i=0;
      }
    else {
      y_i=1;
      }
    act_search_element=act_search_element->sub_element[x_i][y_i];
    }
  if (!colour_found_flag) {
    /* Sould never occur. Only if something is wrong with
       colour tables */
    search->approximation_valid=FALSE;
    return default_mapping;
    }
  /* Sort the edges by distance to get a good approximation. */
  distance_sort_elements=0;
  for (x_i=0; x_i < 8; x_i++) {
    if (best_quarder_colour[x_i].best_colour) {
      i=distance_sort_elements-1;
      while ((i >= 0) &&
             (best_quarder_colour[distance_sort[i]].best_colour_distance > best_quarder_colour[x_i].best_colour_distance)) {
        distance_sort[i + 1]=distance_sort[i];
        i--;
        }
      distance_sort[i + 1]=x_i;
      distance_sort_elements++;
      }
    }
  /* Find out the actual colour from up to eight stored colours */
  occurance_list_pos=0;
  for (x_i=0; x_i < distance_sort_elements; x_i++) {
    i=distance_sort[x_i];
    if (best_quarder_colour[i].best_colour) {
      if (occurance_list_pos == 0) {
        occurance_list[0].original_colour=best_quarder_colour[i].best_colour;
        occurance_list[0].colour[0]=best_quarder_colour[i].best_colour->colour[0];
        occurance_list[0].colour[1]=best_quarder_colour[i].best_colour->colour[1];
        occurance_list[0].colour[2]=best_quarder_colour[i].best_colour->colour[2];
        occurance_list[0].local_usage_percentage=1<<11;
        old_ref_distance=best_quarder_colour[i].best_colour_distance;
        occurance_list_pos=1;
#ifdef RNGS_TRACE_MODE
        sprintf(trace_string,
                "flp: %d RGB: %ld %ld %ld ord: %ld olp: %d\n",
                i,
                best_quarder_colour[i].best_colour->colour[0],
                best_quarder_colour[i].best_colour->colour[1],
                best_quarder_colour[i].best_colour->colour[2],
                old_ref_distance,
                occurance_list_pos);
        regs.r[0]=2;
        regs.r[1]=search->trace_file;
        regs.r[2]=(int) trace_string;
        regs.r[3]=strlen(trace_string);
        _kernel_swi(OS_GBPB, &regs, &regs);
#endif
        }
      else {
        /* Calculate percentage by Phytagoras. This is also valid in 3D:
           a1^2 + b1^2 = c1^2
           a2^2 + b2^2 = c2^2
           c1=c2
           a1 + a2 = s
           s is distance between the points on the main line.
           a2 = s - a1
           a1^2 + b1^2 = a2^2 + b2^2
           a1^2 + b1^2 - b2^2 = (s - a1)^2
           a1^2 + b1^2 - b2^2 = s^2 - 2sa1 + a1^2
           b1^2 - b2^2 - s^2 = - 2sa1
           -(b1^2 - b2^2 - s^2)/2s = a1

           However not a1 but percent in relation to s is needed. This save us sqaure root
           operation:

           -(b1^2 - b2^2 - s^2)/2s^2 = a1/s

           Acceleration:
           b1 has been already calculated during the colour selection process.
           b2 can be obtained on this way also in the first step.

           If s=0 then choose new component b directly.

           Bit range:

           Every distance can 3 * (8 Bit * 8 Bit = 16 Bit) -> 18 leading Bits used
           12 trailing bits are possible. */
        diff_x=best_quarder_colour[i].best_colour->colour[0] - occurance_list[occurance_list_pos - 1].colour[0];
        act_distance=diff_x*diff_x;
        diff_y=best_quarder_colour[i].best_colour->colour[1] - occurance_list[occurance_list_pos - 1].colour[1];
        act_distance+=diff_y*diff_y;
        diff_z=best_quarder_colour[i].best_colour->colour[2] - occurance_list[occurance_list_pos - 1].colour[2];
        act_distance+=diff_z*diff_z;
        if (act_distance != 0) {
          if (occurance_list_pos != 1) {
            diff=occurance_list[occurance_list_pos - 1].colour[0] - x_value;
            old_ref_distance=diff*diff;
            diff=occurance_list[occurance_list_pos - 1].colour[1] - y_value;
            old_ref_distance+=diff*diff;
            diff=occurance_list[occurance_list_pos - 1].colour[2] - z_value;
            old_ref_distance+=diff*diff;
            }
          occurance_list[occurance_list_pos].local_usage_percentage=(1<<11) - (((act_distance + best_quarder_colour[i].best_colour_distance - old_ref_distance)<<11)/(2*act_distance));
          /* Limit local usage percentage to range between the points (0-1) */
          /* Don't take irrelevant points into the list */
          if (occurance_list[occurance_list_pos].local_usage_percentage > 0) {
            if (occurance_list[occurance_list_pos].local_usage_percentage >= (1<<11)) {
              /* Supress all the irrelevant points before */
              occurance_list[0].original_colour=best_quarder_colour[i].best_colour;
              occurance_list[0].colour[0]=best_quarder_colour[i].best_colour->colour[0];
              occurance_list[0].colour[1]=best_quarder_colour[i].best_colour->colour[1];
              occurance_list[0].colour[2]=best_quarder_colour[i].best_colour->colour[2];
              occurance_list[0].local_usage_percentage=1<<11;
              old_ref_distance=best_quarder_colour[i].best_colour_distance;
              occurance_list_pos=1;
#ifdef RNGS_TRACE_MODE
              sprintf(trace_string,
                      "one: %d RGB: %ld %ld %ld ord: %ld olp: %d proz: %f\n",
                      i,
                      best_quarder_colour[i].best_colour->colour[0],
                      best_quarder_colour[i].best_colour->colour[1],
                      best_quarder_colour[i].best_colour->colour[2],
                      old_ref_distance,
                      occurance_list_pos,
                      (double) occurance_list[occurance_list_pos - 1].local_usage_percentage/(1<<11));
              regs.r[0]=2;
              regs.r[1]=search->trace_file;
              regs.r[2]=(int) trace_string;
              regs.r[3]=strlen(trace_string);
              _kernel_swi(OS_GBPB, &regs, &regs);
#endif
              }
            else {
              /* Calculate new point.
                 12 trailing bits. Difference may be negative!
                 So shift also additional value and shift back
                 afterwards. Supressing of top bit should not be
                 necassary because result must be in range 0-255. */
              occurance_list[occurance_list_pos].original_colour=best_quarder_colour[i].best_colour;
              occurance_list[occurance_list_pos].colour[0]=((occurance_list[occurance_list_pos].local_usage_percentage*diff_x) + (occurance_list[occurance_list_pos - 1].colour[0]<<11))>>11;
              occurance_list[occurance_list_pos].colour[1]=((occurance_list[occurance_list_pos].local_usage_percentage*diff_y) + (occurance_list[occurance_list_pos - 1].colour[1]<<11))>>11;
              occurance_list[occurance_list_pos].colour[2]=((occurance_list[occurance_list_pos].local_usage_percentage*diff_z) + (occurance_list[occurance_list_pos - 1].colour[2]<<11))>>11;
              occurance_list_pos++;
#ifdef RNGS_TRACE_MODE
              sprintf(trace_string,
                      "usual: %d RGB: %ld %ld %ld ord: %ld olp: %d proz: %f RGBm: %ld %ld %ld\n",
                      i,
                      best_quarder_colour[i].best_colour->colour[0],
                      best_quarder_colour[i].best_colour->colour[1],
                      best_quarder_colour[i].best_colour->colour[2],
                      old_ref_distance,
                      occurance_list_pos,
                      (double) occurance_list[occurance_list_pos - 1].local_usage_percentage/(1<<11),
                      occurance_list[occurance_list_pos-1].colour[0],
                      occurance_list[occurance_list_pos-1].colour[1],
                      occurance_list[occurance_list_pos-1].colour[2]);
              regs.r[0]=2;
              regs.r[1]=search->trace_file;
              regs.r[2]=(int) trace_string;
              regs.r[3]=strlen(trace_string);
              _kernel_swi(OS_GBPB, &regs, &regs);
#endif
              }
            }
#ifdef RNGS_TRACE_MODE
          else {
            sprintf(trace_string,
                    "ignored: %d RGB: %ld %ld %ld ord: %ld olp: %d proz: %f\n",
                    i,
                    best_quarder_colour[i].best_colour->colour[0],
                    best_quarder_colour[i].best_colour->colour[1],
                    best_quarder_colour[i].best_colour->colour[2],
                    old_ref_distance,
                    occurance_list_pos,
                    (double) occurance_list[occurance_list_pos - 1].local_usage_percentage/(1<<11));
            regs.r[0]=2;
            regs.r[1]=search->trace_file;
            regs.r[2]=(int) trace_string;
            regs.r[3]=strlen(trace_string);
            _kernel_swi(OS_GBPB, &regs, &regs);
            }
#endif
          }
        else {
          /* Supress all the irrelevant points before */
          occurance_list[0].original_colour=best_quarder_colour[i].best_colour;
          occurance_list[0].colour[0]=best_quarder_colour[i].best_colour->colour[0];
          occurance_list[0].colour[1]=best_quarder_colour[i].best_colour->colour[1];
          occurance_list[0].colour[2]=best_quarder_colour[i].best_colour->colour[2];
          occurance_list[0].local_usage_percentage=1<<11;
          old_ref_distance=best_quarder_colour[i].best_colour_distance;
          occurance_list_pos=1;
#ifdef RNGS_TRACE_MODE
          sprintf(trace_string,
                  "exact: %d RGB: %ld %ld %ld ord: %ld olp: %d proz: %f\n",
                  i,
                  best_quarder_colour[i].best_colour->colour[0],
                  best_quarder_colour[i].best_colour->colour[1],
                  best_quarder_colour[i].best_colour->colour[2],
                  old_ref_distance,
                  occurance_list_pos,
                  (double) occurance_list[occurance_list_pos - 1].local_usage_percentage/(1<<11));
          regs.r[0]=2;
          regs.r[1]=search->trace_file;
          regs.r[2]=(int) trace_string;
          regs.r[3]=strlen(trace_string);
          _kernel_swi(OS_GBPB, &regs, &regs);
#endif
          }
        }
      }
    }
#ifdef RNGS_TRACE_MODE
  sprintf(trace_string,
          "real percentages of: %d\n",
          occurance_list_pos);
  regs.r[0]=2;
  regs.r[1]=search->trace_file;
  regs.r[2]=(int) trace_string;
  regs.r[3]=strlen(trace_string);
  _kernel_swi(OS_GBPB, &regs, &regs);
#endif
  /* Calculate total percentage and occurrance */
  dither_paper_colour=NULL;
  dither_paper_colour_fraction=0;
  max_percentage=0;
  search->dither_list_pos=0;
  diff=1<<16;
  i=occurance_list_pos - 1;
  while ((i >= 0) &&
         (diff > (2<<0))) {
    actual_dither_list_element=&search->dither_list[search->dither_list_pos];
    /* 16 trailing Bits from diff and 11 trailing Bits from percentage -> 27 trailing Bits shift by 11 Bits
       -> 16 trailing Bits */
    actual_dither_list_element->total_usage_percentage=(occurance_list[i].local_usage_percentage * diff)>>11;
    if (actual_dither_list_element->total_usage_percentage > (1<<9)) {
      actual_dither_list_element->original_colour=occurance_list[i].original_colour;
      if ((!dither_paper_colour) &&
          ((occurance_list[i].original_colour->group_mask & COLOUR_GROUP_PAPER_COLOUR) != 0)) {
        /* Note whether paper colour element is in the list. */
        dither_paper_colour=actual_dither_list_element;
        }
      /* Subtract all */
      diff-=actual_dither_list_element->total_usage_percentage;
      /* 12 Bits muliplied by 16 trailing Bits -> 28 trailing Bits shifted by 12 Bits -> 16 trailing Bits */
      actual_dither_paper_colour_fraction=(actual_dither_list_element->total_usage_percentage*actual_dither_list_element->original_colour->paper_colour_fraction)>>12;
      dither_paper_colour_fraction+=actual_dither_paper_colour_fraction;
      actual_dither_list_element->total_usage_percentage-=actual_dither_paper_colour_fraction;
      if (actual_dither_list_element->total_usage_percentage > (1<<9)) {
        /* Max Percentage of the reduced value */
        if (max_percentage < actual_dither_list_element->total_usage_percentage) {
          max_percentage=actual_dither_list_element->total_usage_percentage;
          }
        /* 27 trailing Bits divided by 16 trailing Bits -> 11 trailing Bits */
        actual_dither_list_element->occurrance=(1<<27)/actual_dither_list_element->total_usage_percentage;
#ifdef RNGS_TRACE_MODE
        sprintf(trace_string,
                "step: %d dp: %d diff: %f proz: %f max: %f occurance; %f RGB: %d %d %d\n",
                i,
                search->dither_list_pos,
                (double) diff/(1<<16),
                (double) actual_dither_list_element->total_usage_percentage/(1<<16),
                (double) max_percentage/(1<<16),
                (double) actual_dither_list_element->occurrance/(1<<11),
                actual_dither_list_element->original_colour->colour[0],
                actual_dither_list_element->original_colour->colour[1],
                actual_dither_list_element->original_colour->colour[2]);
        regs.r[0]=2;
        regs.r[1]=search->trace_file;
        regs.r[2]=(int) trace_string;
        regs.r[3]=strlen(trace_string);
        _kernel_swi(OS_GBPB, &regs, &regs);
#endif
        search->dither_list_pos++;
        }
      }
    i--;
    }
  /* Correct/build paper colour fraction if required */
  if (dither_paper_colour_fraction > (1<<9)) {
    if (!dither_paper_colour) {
      /* Paper colour must be added */
      actual_dither_list_element=&search->dither_list[search->dither_list_pos];
      actual_dither_list_element->original_colour=search->paper_colour;
      actual_dither_list_element->total_usage_percentage=dither_paper_colour_fraction;
      if (max_percentage < actual_dither_list_element->total_usage_percentage) {
        max_percentage=actual_dither_list_element->total_usage_percentage;
        }
      /* 27 trailing Bits divided by 16 trailing Bits -> 11 trailing Bits */
      actual_dither_list_element->occurrance=(1<<27)/actual_dither_list_element->total_usage_percentage;
      search->dither_list_pos++;
      }
    else {
      /* Enhance and recalculate existing paper colour */
      dither_paper_colour->total_usage_percentage+=dither_paper_colour_fraction;
      if (max_percentage < dither_paper_colour->total_usage_percentage) {
        max_percentage=dither_paper_colour->total_usage_percentage;
        }
      /* 27 trailing Bits divided by 16 trailing Bits -> 11 trailing Bits */
      dither_paper_colour->occurrance=(1<<27)/dither_paper_colour->total_usage_percentage;
      }
    }
  /* Calculate the relation between the colours and
     add these factor to obtain a factor for the element with the
     highest occurance */
  search->base_factor=0;
  search->approximation_remain=0;
  for (i=0; i < search->dither_list_pos; i++) {
    search->approximation_remain+=search->dither_list[i].occurrance;
    /* 16 + 11 trailing Bits divided by 16 trailing Bits -> 11 trailing Bits */
    search->dither_list[i].relation_factor=(search->dither_list[i].total_usage_percentage<<11)/max_percentage;
    search->base_factor+=search->dither_list[i].relation_factor;
#ifdef RNGS_TRACE_MODE
    sprintf(trace_string,
            "relation: %d rf: %f bf: %f\n",
            i,
            (double) search->dither_list[i].relation_factor/(1<<11),
            (double) search->base_factor/(1<<11));
    regs.r[0]=2;
    regs.r[1]=search->trace_file;
    regs.r[2]=(int) trace_string;
    regs.r[3]=strlen(trace_string);
    _kernel_swi(OS_GBPB, &regs, &regs);
#endif
    }
  if ((search->approximation_remain & 0x000007FF) > 0x000003FF) {
    search->approximation_remain=(search->approximation_remain>>11) + 1;
    }
  else {
    search->approximation_remain>>=11;
    }
  search->last_colour_component[0]=x_value;
  search->last_colour_component[1]=y_value;
  search->last_colour_component[2]=z_value;
  search->approximation_valid=TRUE;
  /* Limit approximation usage to often occuring patterns */
  if (search->approximation_remain > 5) {
    search->approximation_remain=0;
    }
  }
/* 0 + 22 trailings Bits divided by 11 trailing Bits -> 11 trailing Bits */
if (pixel_position >= search->dither_list_pos) {
  main_factor=((pixel_position - search->dither_list_pos)<<22)/search->base_factor;
  }
else {
  main_factor=0;
  }
#ifdef RNGS_TRACE_MODE
sprintf(trace_string,
        "main factor: %f %lx pp: %ld dp: %d bf: %ld %f\n",
        (double) main_factor/(1<<11),
        main_factor,
        pixel_position,
        search->dither_list_pos,
        search->base_factor,
        (double) search->base_factor/(1<<11));
regs.r[0]=2;
regs.r[1]=search->trace_file;
regs.r[2]=(int) trace_string;
regs.r[3]=strlen(trace_string);
_kernel_swi(OS_GBPB, &regs, &regs);
#endif
number_of_best_colours=0;
max_position=0;
actual_sum=0;
for (i=0; i < search->dither_list_pos; i++) {
  /* 11 trailing Bits multiplied by 11 trailing Bits -> 22 trailing Bits but 0 required */
  search->dither_list[i].integer_factor=(main_factor*search->dither_list[i].relation_factor)>>22;
  search->dither_list[i].position=search->dither_list[i].integer_factor*search->dither_list[i].occurrance;
if (((search->dither_list[i].occurrance & 0x000007FF) != 0) &&
    ((search->dither_list[i].occurrance>>11) < (NUMBER_OF_OCCURANCES - 1))) {
  x_i=(search->actual_line*NUMBER_OF_OCCURANCES) + (search->dither_list[i].occurrance>>11) + 1;
  }
else {
  x_i=(search->actual_line*NUMBER_OF_OCCURANCES) + (search->dither_list[i].occurrance>>11);
  }
/* x_i=0 */
  line_position_offset=(search->line_offset[x_i]<<11);
#ifdef RNGS_TRACE_MODE
  sprintf(trace_string,
          "lpo: %d al: %ld occ: %lx lpo: %d ae: %d aev: %lx\n",
          i,
          search->actual_line,
          search->dither_list[i].occurrance,
          line_position_offset,
          x_i,
          search->line_offset[x_i]);
  regs.r[0]=2;
  regs.r[1]=search->trace_file;
  regs.r[2]=(int) trace_string;
  regs.r[3]=strlen(trace_string);
  _kernel_swi(OS_GBPB, &regs, &regs);
#endif
  if (line_position_offset != 0) {
    search->dither_list[i].integer_factor--;
    search->dither_list[i].position+=line_position_offset - search->dither_list[i].occurrance;
    }
  if (max_position == search->dither_list[i].position) {
    best_colour[number_of_best_colours]=search->dither_list[i].original_colour;
    number_of_best_colours++;
    }
  else if (max_position < search->dither_list[i].position) {
    max_position=search->dither_list[i].position;
    best_colour[0]=search->dither_list[i].original_colour;
    number_of_best_colours=1;
    }
  if (search->dither_list[i].integer_factor < 0) {
    if (search->dither_list[i].position >= 0) {
      actual_sum++;
      }
    }
  else {
    actual_sum+=search->dither_list[i].integer_factor + 1;
    }
#ifdef RNGS_TRACE_MODE
  sprintf(trace_string,
          "1st approx: %d int: %ld pos: %f off: %f %d max_pos: %f nbc: %d\n",
          i,
          search->dither_list[i].integer_factor,
          (double) search->dither_list[i].position/(1<<11),
          (double) line_position_offset/(1<<11),
          search->actual_line,
          (double) max_position/(1<<11),
          number_of_best_colours);
  regs.r[0]=2;
  regs.r[1]=search->trace_file;
  regs.r[2]=(int) trace_string;
  regs.r[3]=strlen(trace_string);
  _kernel_swi(OS_GBPB, &regs, &regs);
#endif
  }
while (actual_sum < pixel_position) {
#ifdef RNGS_TRACE_MODE
  sprintf(trace_string,
          "last loop: sum: %ld pos: %ld max_pos: %f\n",
          actual_sum,
          pixel_position,
          (double) max_position/(1<<11));
  regs.r[0]=2;
  regs.r[1]=search->trace_file;
  regs.r[2]=(int) trace_string;
  regs.r[3]=strlen(trace_string);
  _kernel_swi(OS_GBPB, &regs, &regs);
#endif
  min_position=0x0FFFFFFF;
  for (i=0; i < search->dither_list_pos; i++) {
    if (search->dither_list[i].position <= max_position) {
      search->dither_list[i].integer_factor++;
      search->dither_list[i].position+=search->dither_list[i].occurrance;
#ifdef RNGS_TRACE_MODE
      sprintf(trace_string,
              "increase: %d int: %ld pos: %f\n",
              i,
              search->dither_list[i].integer_factor,
              (double) search->dither_list[i].position/(1<<11));
      regs.r[0]=2;
      regs.r[1]=search->trace_file;
      regs.r[2]=(int) trace_string;
      regs.r[3]=strlen(trace_string);
      _kernel_swi(OS_GBPB, &regs, &regs);
#endif
      }
    if (min_position == search->dither_list[i].position) {
#ifdef RNGS_TRACE_MODE
      sprintf(trace_string,
              "eqadd: %d pos: %f RGB: %d %d %d\n",
              i,
              (double) search->dither_list[i].position/(1<<11),
              search->dither_list[i].original_colour->colour[0],
              search->dither_list[i].original_colour->colour[1],
              search->dither_list[i].original_colour->colour[2]);
      regs.r[0]=2;
      regs.r[1]=search->trace_file;
      regs.r[2]=(int) trace_string;
      regs.r[3]=strlen(trace_string);
      _kernel_swi(OS_GBPB, &regs, &regs);
#endif
      best_colour[number_of_best_colours]=search->dither_list[i].original_colour;
      number_of_best_colours++;
      }
    else if (min_position > search->dither_list[i].position) {
#ifdef RNGS_TRACE_MODE
      sprintf(trace_string,
              "better: %d pos: %f RGB: %d %d %d\n",
              i,
              (double) search->dither_list[i].position/(1<<11),
              search->dither_list[i].original_colour->colour[0],
              search->dither_list[i].original_colour->colour[1],
              search->dither_list[i].original_colour->colour[2]);
      regs.r[0]=2;
      regs.r[1]=search->trace_file;
      regs.r[2]=(int) trace_string;
      regs.r[3]=strlen(trace_string);
      _kernel_swi(OS_GBPB, &regs, &regs);
#endif
      min_position=search->dither_list[i].position;
      best_colour[0]=search->dither_list[i].original_colour;
      number_of_best_colours=1;
      }
    }
  actual_sum+=number_of_best_colours;
  max_position=min_position;
  }
if (number_of_best_colours > 0) {
  i=(pixel_position + (search->actual_line & 0x00000007))%number_of_best_colours;
/*if (number_of_best_colours > 1) {
  return 0x00FF0000;
  }
for (i=0; i < search->dither_list_pos; i++) {
  if (best_colour[0] == search->dither_list[i].original_colour) {
    if (search->dither_list[i].occurrance <= 0x00000A00) {
      return 0x0000FF00;
      }
    else if (search->dither_list[i].occurrance < 0x00000C00) {
      return 0x000000FF;
      }
    }
  }
i=0;*/
  if (mode == 3) {
    return best_colour[i]->colour[0] | (best_colour[i]->colour[1]<<8) | (best_colour[i]->colour[2]<<16);
    }
  else {
    return best_colour[i]->colour_mapping;
    }
  }
else {
  return default_mapping;
  }
}

#endif
